package 剑指Offer._0110;

import general_class.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/7/5 21:16
 * 重建二叉树
 * 算法：二叉树
 * 前序遍历：根 - 左 - 右
 * 中序遍历：左 - 根 - 右
 * 根据前序遍历，可以找到根节点
 * 知道根节点后，根据中序遍历可以知道左右子树的数量
 */
public class _07 {
    public static void main(String[] args) {
        System.out.println(new _07().buildTree(new int[]{3, 9, 20, 15, 7},
                new int[]{9, 3, 15, 20, 7}));
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        if (len == 0) return null;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) map.put(inorder[i], i);
        return getRoot(preorder, 0, len - 1,
                0, map);
    }
    TreeNode getRoot(int[] preorder, int preBegin, int preEnd, int inBegin,
                     Map<Integer, Integer> map) {
        if (preBegin > preEnd) return null;
        TreeNode root = new TreeNode(preorder[preBegin]);
        // inorder 中根节点的位置
        int idx = map.get(preorder[preBegin]);
        int leftSize = idx - inBegin;
        // 左子树在 preOrder 和 inOrder 的范围
        root.left = getRoot(preorder, preBegin + 1, preBegin + leftSize,
                inBegin, map);
        // 同理
        root.right = getRoot(preorder, preBegin + leftSize + 1, preEnd,
                idx + 1, map);
        return root;
    }

}
